package dynamic;

import lombok.extern.slf4j.Slf4j;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

/**
 * @author 罗俊华
 * @date 2022/1/5 - 8:54 上午
 */
@Slf4j
public class Sequence {

    public int[] sourceArray;


    public Sequence() {
    }


    @DisplayName("找出连续子序列的最大和")
    @Test
    public void test() {

        Sequence sequence = new Sequence();
//        sequence.sourceArray = new int[]{3, -4, 2, -1, 2, 6, -5, 4}; // 答案是：9
        sequence.sourceArray = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}; // 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

        int result = sequence.maxSum();
        log.info("结果是：{}", result);
    }

    /**
     * 连续子数组的最大和
     * 动态规划算法
     *
     * @return
     */
    public int maxSum() {
        int max = Integer.MIN_VALUE;
        Integer[] cacheArray = new Integer[sourceArray.length];

//        从后往前计算，无需使用递归，而且可以缓存数据
        for (int i = sourceArray.length - 1; i >= 0; i--) {
            max = Math.max(maxSumByDynamic(i, cacheArray), max);
        }
        return max;
    }

    private int maxSumByDynamic(int startIndex, Integer[] cacheArray) {

        if (startIndex == sourceArray.length - 1) {
            cacheArray[sourceArray.length - 1] = sourceArray[sourceArray.length - 1];
            return sourceArray[sourceArray.length - 1];
        }

        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = startIndex; i < sourceArray.length; i++) {

//            试图从缓存中拿出数据
            Integer cache = cacheArray[i];
            if (cache != null) {
                log.info("startIndex={}的缓存命中，缓存内容为：{}", i, cache);
                sum += cache;
                max = Math.max(sum, max);
                break;
            }
            sum += sourceArray[i];
            max = Math.max(sum, max);
        }
//        将结果放入缓存
        cacheArray[startIndex] = max;
        return max;
    }

    /**
     * 暴力匹配算法实现
     *
     * @param startIndex
     * @param cacheArray
     * @return
     */
    private int maxSumByViolence(int startIndex, Integer[] cacheArray) {

        if (startIndex == sourceArray.length - 1) {
            return sourceArray[sourceArray.length - 1];
        }

        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = startIndex; i < sourceArray.length; i++) {
            sum += sourceArray[i];
            max = Math.max(sum, max);
        }

        return max;
    }


}
